# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        root_max, root_node = self.maxPathSumAndNodeSum(root)
        return root_max

    def maxPathSumAndNodeSum(self, root):
        if root is None:
            return None, None
        left_max, left_node = self.maxPathSumAndNodeSum(root.left)
        right_max, right_node = self.maxPathSumAndNodeSum(root.right)

        root_max = root.val
        root_node = root.val
        all_val = root.val

        if left_node is not None:
            root_node = max(root.val + left_node, root_node)
            all_val = max(all_val + left_node, all_val)
        if right_node is not None:
            root_node = max(root.val + right_node, root_node)
            all_val = max(all_val + right_node, all_val)

        if left_max is not None:
            root_max = max(left_max, root_max)
        if right_max is not None:
            root_max = max(right_max, root_max)

        root_max = max(all_val, root_max)

        return root_max, root_node



if __name__ == '__main__':
    so = Solution()
    root = TreeNode(1)
    root.left = TreeNode(1)
    root.left.right = TreeNode(-5)
    root.right = TreeNode(10)
    r = so.maxPathSum(root)
    print(r)

